<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>布隆过滤器 - 高效集合查询算法</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            color: #333;
            line-height: 1.6;
        }
        h1, h2, h3, h4 {
            font-family: 'Noto Serif SC', serif;
            font-weight: 600;
        }
        .hero {
            height: 60vh;
            background: linear-gradient(135deg, #6e8efb 0%, #a777e3 100%);
            clip-path: polygon(0 0, 100% 0, 100% 85%, 0 100%);
        }
        .code-block {
            background: #2d3748;
            border-left: 4px solid #a777e3;
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .highlight {
            position: relative;
        }
        .highlight:after {
            content: '';
            position: absolute;
            bottom: 0;
            left: 0;
            width: 100%;
            height: 30%;
            background: rgba(167, 119, 227, 0.2);
            z-index: -1;
        }
        .first-letter::first-letter {
            font-size: 3.5rem;
            font-weight: bold;
            float: left;
            line-height: 0.8;
            margin-right: 0.5rem;
            color: #6e8efb;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <div class="hero flex items-center justify-center text-white">
        <div class="container px-6 md:px-12 text-center">
            <h1 class="text-4xl md:text-6xl font-bold mb-6 animate-fade-in-down">布隆过滤器</h1>
            <p class="text-xl md:text-2xl max-w-3xl mx-auto mb-8 opacity-90">
                空间效率极高的概率型数据结构，实现快速元素存在性判断
            </p>
            <div class="inline-flex items-center space-x-2 bg-white bg-opacity-20 px-4 py-2 rounded-full">
                <i class="fas fa-bolt text-yellow-300"></i>
                <span>时间复杂度: O(k) | 空间复杂度: O(m)</span>
            </div>
        </div>
    </div>

    <!-- Main Content -->
    <div class="container mx-auto px-6 md:px-12 py-16 -mt-20 relative z-10">
        <!-- Introduction -->
        <div class="bg-white rounded-xl shadow-lg p-8 mb-16 card-hover">
            <div class="flex items-start">
                <div class="hidden md:block mr-8">
                    <div class="w-32 h-32 bg-purple-100 rounded-full flex items-center justify-center">
                        <i class="fas fa-filter text-5xl text-purple-600"></i>
                    </div>
                </div>
                <div>
                    <h2 class="text-2xl md:text-3xl font-bold mb-4 text-gray-800">布隆过滤器简介</h2>
                    <p class="first-letter text-gray-700 mb-6">
                        布隆过滤器是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。它的核心思想是使用一个位数组和多个哈希函数，通过将元素映射到位数组的不同位置来实现快速查询。布隆过滤器具有很小的误判率，但不会漏判，广泛应用于缓存系统、数据库系统和网络爬虫等领域。
                    </p>
                    <div class="bg-blue-50 border-l-4 border-blue-500 p-4 rounded-r">
                        <div class="flex">
                            <div class="flex-shrink-0">
                                <i class="fas fa-info-circle text-blue-500"></i>
                            </div>
                            <div class="ml-3">
                                <p class="text-sm text-blue-700">
                                    关键特性：空间效率极高、快速查询、允许误判但不会漏判
                                </p>
                            </div>
                        </div>
                    </div>
                </div>
            </div>
        </div>

        <!-- Features Section -->
        <div class="grid md:grid-cols-3 gap-8 mb-16">
            <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                <div class="text-purple-600 mb-4">
                    <i class="fas fa-clock text-3xl"></i>
                </div>
                <h3 class="text-xl font-bold mb-3 text-gray-800">高效查询</h3>
                <p class="text-gray-600">插入和查询操作的时间复杂度均为O(k)，其中k是哈希函数的个数，查询速度极快。</p>
            </div>
            <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                <div class="text-purple-600 mb-4">
                    <i class="fas fa-database text-3xl"></i>
                </div>
                <h3 class="text-xl font-bold mb-3 text-gray-800">空间节省</h3>
                <p class="text-gray-600">相比传统数据结构，布隆过滤器可以节省大量内存空间，空间复杂度为O(m)，m是位数组大小。</p>
            </div>
            <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                <div class="text-purple-600 mb-4">
                    <i class="fas fa-balance-scale text-3xl"></i>
                </div>
                <h3 class="text-xl font-bold mb-3 text-gray-800">概率特性</h3>
                <p class="text-gray-600">可能存在误判（假阳性），但不会漏判（假阴性），误判率可通过参数调节。</p>
            </div>
        </div>

        <!-- Algorithm Explanation -->
        <div class="mb-16">
            <h2 class="text-3xl font-bold mb-8 text-gray-800 relative">
                <span class="highlight">算法原理</span>
            </h2>
            
            <!-- Mermaid Diagram -->
            <div class="mb-12 bg-white p-6 rounded-xl shadow-md">
                <div class="mermaid">
                    graph LR
                    A[输入元素] --> B[哈希函数1]
                    A --> C[哈希函数2]
                    A --> D[哈希函数3]
                    B --> E[位数组位置1]
                    C --> F[位数组位置2]
                    D --> G[位数组位置3]
                    E --> H[设置位为1]
                    F --> H
                    G --> H
                    H --> I[查询结果]
                </div>
            </div>

            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                    <h3 class="text-xl font-bold mb-4 text-gray-800 flex items-center">
                        <i class="fas fa-plus-circle text-purple-600 mr-2"></i> 插入过程
                    </h3>
                    <ol class="list-decimal pl-5 space-y-2 text-gray-700">
                        <li>使用k个不同的哈希函数计算元素的哈希值</li>
                        <li>将位数组中对应的k个位置设置为1</li>
                        <li>完成元素的插入</li>
                    </ol>
                </div>
                <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                    <h3 class="text-xl font-bold mb-4 text-gray-800 flex items-center">
                        <i class="fas fa-search text-purple-600 mr-2"></i> 查询过程
                    </h3>
                    <ol class="list-decimal pl-5 space-y-2 text-gray-700">
                        <li>使用相同的k个哈希函数计算元素的哈希值</li>
                        <li>检查位数组中对应的k个位置是否都为1</li>
                        <li>如果所有位都为1，元素可能存在；如有任一位为0，元素一定不存在</li>
                    </ol>
                </div>
            </div>
        </div>

        <!-- Code Implementation -->
        <div class="mb-16">
            <h2 class="text-3xl font-bold mb-8 text-gray-800 relative">
                <span class="highlight">Java实现</span>
            </h2>
            
            <div class="bg-white rounded-xl shadow-lg overflow-hidden">
                <div class="bg-gray-800 px-4 py-3 flex items-center">
                    <div class="flex space-x-2 mr-4">
                        <span class="w-3 h-3 rounded-full bg-red-500"></span>
                        <span class="w-3 h-3 rounded-full bg-yellow-500"></span>
                        <span class="w-3 h-3 rounded-full bg-green-500"></span>
                    </div>
                    <div class="text-white text-sm font-mono">BloomFilter.java</div>
                </div>
                <div class="code-block p-6 overflow-x-auto">
                    <pre class="text-gray-100"><code>
import java.util.BitSet;

/**
 * 布隆过滤器实现
 * 用于快速判断一个元素是否在一个集合中
 */
public class BloomFilter {
    // 位数组，用于存储元素的哈希值
    private BitSet bitSet;
    // 位数组的大小
    private int size;
    // 哈希函数的个数
    private int hashFunctions;
    
    /**
     * 构造函数
     * @param size 位数组的大小
     * @param hashFunctions 哈希函数的个数
     */
    public BloomFilter(int size, int hashFunctions) {
        this.size = size;
        this.hashFunctions = hashFunctions;
        this.bitSet = new BitSet(size);
    }
    
    /**
     * 将元素添加到布隆过滤器中
     * @param element 要添加的元素
     */
    public void add(String element) {
        // 使用多个哈希函数计算元素的哈希值，并将对应位置为1
        for (int i = 0; i < hashFunctions; i++) {
            int hash = getHash(element, i);
            bitSet.set(hash);
        }
    }
    
    /**
     * 判断元素是否可能在集合中
     * @param element 要判断的元素
     * @return 如果元素可能在集合中，返回true；如果元素一定不在集合中，返回false
     */
    public boolean mightContain(String element) {
        // 使用多个哈希函数计算元素的哈希值，检查对应位是否都为1
        for (int i = 0; i < hashFunctions; i++) {
            int hash = getHash(element, i);
            // 如果有任一位为0，则元素一定不在集合中
            if (!bitSet.get(hash)) {
                return false;
            }
        }
        // 所有位都为1，元素可能在集合中（存在误判的可能）
        return true;
    }
    
    /**
     * 计算元素在第i个哈希函数下的哈希值
     * @param element 要计算哈希值的元素
     * @param i 哈希函数的索引
     * @return 哈希值
     */
    private int getHash(String element, int i) {
        // 使用不同的哈希种子计算哈希值
        int hash = element.hashCode();
        // 使用不同的乘数和加数来产生不同的哈希函数
        hash = hash * 31 * (i + 1) + 17;
        // 取模确保哈希值在位数组范围内
        return Math.abs(hash % size);
    }
    
    /**
     * 获取布隆过滤器的预估误判率
     * @param n 插入的元素数量
     * @return 误判率
     */
    public double getFalsePositiveProbability(int n) {
        // 计算误判率的公式：(1 - e^(-k*n/m))^k
        // 其中k是哈希函数个数，n是插入元素个数，m是位数组大小
        double exponent = -1.0 * hashFunctions * n / size;
        return Math.pow(1 - Math.exp(exponent), hashFunctions);
    }
    
    /**
     * 使用示例
     */
    public static void main(String[] args) {
        // 创建一个布隆过滤器，大小为1000，使用3个哈希函数
        BloomFilter filter = new BloomFilter(1000, 3);
        
        // 添加元素
        filter.add("apple");
        filter.add("banana");
        filter.add("orange");
        
        // 检查元素是否在集合中
        System.out.println("apple 可能在集合中: " + filter.mightContain("apple"));    // true
        System.out.println("banana 可能在集合中: " + filter.mightContain("banana"));  // true
        System.out.println("pear 可能在集合中: " + filter.mightContain("pear"));      // false
        
        // 计算误判率
        System.out.println("插入3个元素后的误判率: " + filter.getFalsePositiveProbability(3));
    }
}
                    </code></pre>
                </div>
            </div>
        </div>

        <!-- Performance Analysis -->
        <div class="mb-16">
            <h2 class="text-3xl font-bold mb-8 text-gray-800 relative">
                <span class="highlight">性能分析</span>
            </h2>
            
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white p-6 rounded-xl shadow-md">
                    <h3 class="text-xl font-bold mb-4 text-gray-800 flex items-center">
                        <i class="fas fa-chart-line text-purple-600 mr-2"></i> 误判率计算
                    </h3>
                    <p class="text-gray-700 mb-4">布隆过滤器的误判率可以通过以下公式计算：</p>
                    <div class="bg-gray-100 p-4 rounded-lg font-mono mb-4">
                        (1 - e<sup>-kn/m</sup>)<sup>k</sup>
                    </div>
                    <p class="text-gray-700">
                        其中k是哈希函数个数，n是插入元素个数，m是位数组大小。通过调整这三个参数，可以平衡空间效率和误判率。
                    </p>
                </div>
                
                <div class="bg-white p-6 rounded-xl shadow-md">
                    <h3 class="text-xl font-bold mb-4 text-gray-800 flex items-center">
                        <i class="fas fa-cogs text-purple-600 mr-2"></i> 参数选择
                    </h3>
                    <ul class="list-disc pl-5 space-y-2 text-gray-700">
                        <li><strong>位数组大小 (m):</strong> 越大误判率越低，但内存占用越大</li>
                        <li><strong>哈希函数数量 (k):</strong> 通常取(m/n)*ln2时最佳</li>
                        <li><strong>元素数量 (n):</strong> 与误判率成正比</li>
                    </ul>
                </div>
            </div>
        </div>

        <!-- Applications -->
        <div class="mb-16">
            <h2 class="text-3xl font-bold mb-8 text-gray-800 relative">
                <span class="highlight">应用场景</span>
            </h2>
            
            <div class="grid md:grid-cols-3 gap-6">
                <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                    <div class="text-purple-600 mb-3">
                        <i class="fas fa-server text-2xl"></i>
                    </div>
                    <h3 class="text-lg font-bold mb-2 text-gray-800">缓存系统</h3>
                    <p class="text-gray-600">用于快速判断数据是否在缓存中，避免不必要的磁盘或数据库查询。</p>
                </div>
                <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                    <div class="text-purple-600 mb-3">
                        <i class="fas fa-spider text-2xl"></i>
                    </div>
                    <h3 class="text-lg font-bold mb-2 text-gray-800">网络爬虫</h3>
                    <p class="text-gray-600">用于记录已访问的URL，避免重复爬取相同页面。</p>
                </div>
                <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                    <div class="text-purple-600 mb-3">
                        <i class="fas fa-shield-alt text-2xl"></i>
                    </div>
                    <h3 class="text-lg font-bold mb-2 text-gray-800">安全防护</h3>
                    <p class="text-gray-600">用于检测恶意URL或垃圾邮件，快速过滤可疑内容。</p>
                </div>
                <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                    <div class="text-purple-600 mb-3">
                        <i class="fas fa-database text-2xl"></i>
                    </div>
                    <h3 class="text-lg font-bold mb-2 text-gray-800">数据库系统</h3>
                    <p class="text-gray-600">用于快速判断记录是否存在，减少不必要的磁盘I/O操作。</p>
                </div>
                <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                    <div class="text-purple-600 mb-3">
                        <i class="fas fa-network-wired text-2xl"></i>
                    </div>
                    <h3 class="text-lg font-bold mb-2 text-gray-800">分布式系统</h3>
                    <p class="text-gray-600">用于判断数据是否在远程节点上，减少网络通信开销。</p>
                </div>
                <div class="bg-white p-6 rounded-xl shadow-md card-hover">
                    <div class="text-purple-600 mb-3">
                        <i class="fas fa-bug text-2xl"></i>
                    </div>
                    <h3 class="text-lg font-bold mb-2 text-gray-800">拼写检查</h3>
                    <p class="text-gray-600">用于快速判断单词是否在字典中，提高拼写检查效率。</p>
                </div>
            </div>
        </div>
    </div>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>